package com.njupt.Tree;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/6 21:38
 * @Description: 701. 二叉搜索树中的插入操作
 * @Version: 1.0
 */


public class InsertIntoBST {

    /**
     * 法一：通过找到要插入节点的位置，完成节点的插入操作
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST1(TreeNode root, int val) {

        if(root == null){
            return new TreeNode(val);
        }
        traverse(root,val);
       return root;
    }

    private void traverse(TreeNode root, int val) {
        //找到要插入的位置则返回
        if(root.left == null  && val < root.val){
            root.left = new TreeNode(val);
            return;
        }else if(root.right == null && val > root.val){
            root.right = new TreeNode(val);
            return;
        }
        //查抄要插入姐弟啊的位置，小于根节点则在左子树上查找
        if(val< root.val){
            traverse(root.left,val);
        }
        //大于根节点则在右子树上查找
        if(val>root.val){
            traverse(root.right,val);
        }

    }

    /**
     * 用递归函数的返回值来完成父子节点的赋值操作
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            TreeNode node = new TreeNode(val);
            return node;
        }
        if(val < root.val){
            root.left = insertIntoBST(root.left,val);
        }
        if(val > root.val){
            root.right = insertIntoBST(root.right,val);
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        InsertIntoBST test = new InsertIntoBST();
        TreeNode treeNode = test.insertIntoBST(root, 5);
        System.out.println();

    }
}
